// https://leetcode.cn/problems/sum-of-all-subset-xor-totals/

// 题干：一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
//       例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
//       给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
//       注意：在本题中，元素 相同 的不同子集应 多次 计数。
//       数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

// 示例：输入：nums = [1,3]
//       输出：6

// 碎语：包含求子集，可以利用“子集”问题来求解
//       回溯很有意思，根据消消乐原理，再次异或一次原来的数字

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int sum;
    int path;
public:
    Solution() : sum(0), path(0) {} // 初始化
    int subsetXORSum(vector<int>& nums)
    {
        dfs(nums, 0);
        return sum;
    }

    void dfs(vector<int>& nums, int pos)
    {
        sum += path;
        for (int i = pos ; i < nums.size() ; i++){
            path ^= nums[i];
            dfs(nums, i + 1);
            path ^= nums[i]; // 回溯
        }
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,3};

    int index = sol.subsetXORSum(nums);
    cout << index << endl;

    return 0;
}